package com.wang.transfer.util.algorithm;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 两数相加
 */
public class TwoAdd {

    public static void main(String[] args) {
        int[] i1 = {2,4,3};
        int[] i2 = {5,6,4};
        ListNode l1 = null;
        for (int i = i1.length - 1; i >= 0; i--) {
            l1 = new ListNode(i1[i], l1);
        }
        ListNode l2 = null;
        for (int i = i2.length - 1; i >= 0; i--) {
            l2 = new ListNode(i2[i], l2);
        }
//        ListNode listNode = new TwoAdd().addTwoNumbers(l1, l2);
        ListNode listNode1 = new TwoAdd().addTwoNumbers2(l1, l2);
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        List<Integer> i1 = new ArrayList<>();
        ListNode n1 = l1;
        do {
            i1.add(n1.val);
        } while ((n1 = n1.next) != null);
        List<Integer> i2 = new ArrayList<>();
        ListNode n2 = l2;
        do {
            i2.add(n2.val);
        } while ((n2 = n2.next) != null);

        int max = Math.max(i1.size(), i2.size());
        int duo = 0;
        List<Integer> ad = new ArrayList<>();
        for (int i = 0; i < max; i++) {
            int ii, jj;
            if (i >= i1.size()) {
                ii = 0;
            } else {
                ii = i1.get(i);
            }
            if (i >= i2.size()) {
                jj = 0;
            } else {
                jj = i2.get(i);
            }
            int i3 = ii + jj + duo;
            ad.add(i3 % 10);
            duo = i3 / 10;
        }
        if (duo != 0) {
            ad.add(duo);
        }
        ListNode listNode = null;
        for (int i = ad.size() - 1; i >= 0; i--) {
            listNode = new ListNode(ad.get(i), listNode);
        }
        return listNode;
    }

    /**
     * 执行结果：通过
     * 显示详情 添加备注
     * 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：41.3 MB, 在所有 Java 提交中击败了79.16%的用户
     * 通过测试用例：1568 / 1568
     */
    public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        int duo = 0;
        List<Integer> ls = new ArrayList<>();
        do {
            int ii, jj;
            ii = l1 != null ? l1.val : 0;
            jj = l2 != null ? l2.val : 0;
            int i3 = ii + jj + duo;
            ls.add(i3 % 10);
            duo = i3 / 10;
            l1 = l1 != null ? l1.next : null;
            l2 = l2 != null ? l2.next : null;
        } while (l1 != null || l2 != null);
        if (duo != 0) ls.add(duo);

        ListNode listNode = null;
        for (int i = ls.size() - 1; i >= 0; i--) {
            listNode = new ListNode(ls.get(i), listNode);
        }
        return listNode;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
